package 面试题22_链表中倒数第k个节点;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 9:28 2021/3/11
 * @Description： 双指针实现，保持两个指针之间间隔为k-1
 * <p>
 * 3个注意点：
 * 1.链表为空
 * 2.k<=0
 * 3.k<n。这一点需要在遍历过程中才能确定
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class Solution {

    public ListNode getKthFromEnd(ListNode head, int k) {

        // 两个特殊输入：链表为空、k<=0
        if (head == null || k <= 0) {
            return null;
        }

        ListNode pAhead = head;
        ListNode pBehind;

        for (int i = 0; i < k - 1; i++) {

            // 检查k是否小于n
            if (pAhead.next != null) {
                pAhead = pAhead.next;
            } else {
                return null;
            }
        }

        pBehind = head;
        while (pAhead.next != null) {
            pAhead = pAhead.next;
            pBehind = pBehind.next;
        }

        return pBehind;

    }
}
